package greed;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Classname : MeetingRoomsII
 * @Description : 253. 会议室 II
 * https://leetcode.cn/problems/meeting-rooms-ii/
 * @Author : cty
 * @Date 2023/4/4 20:33
 */


public class MeetingRoomsII {
    public int minMeetingRooms(int[][] intervals) {
        // order by start, end
        Arrays.sort(intervals, (o1, o2)->{
            if (o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]);
            else return Integer.compare(o1[0], o2[0]);
        });

        // 优先级队列中存放了每个会议室的最近可用时间
        Queue<Integer> q = new PriorityQueue<>();
        q.add(0);

        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] >= q.element()) {
                q.remove();
            }
            q.add(intervals[i][1]);
        }
        return q.size();
    }
}
